{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Factorial Trailing Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trailingZeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #阶乘后的零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数 <code>n</code> ，返回 <code>n!</code> 结果中尾随零的数量。</p>\n",
    "\n",
    "<p>提示&nbsp;<code>n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1</code></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>3! = 6 ，不含尾随 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>5! = 120 ，有一个尾随 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>进阶：</b>你可以设计并实现对数时间复杂度的算法来解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [factorial-trailing-zeroes](https://leetcode.cn/problems/factorial-trailing-zeroes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [factorial-trailing-zeroes](https://leetcode.cn/problems/factorial-trailing-zeroes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '5', '0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        m = 0\n",
    "        while n > 0:\n",
    "            m += n//5\n",
    "            n = n//5\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        else:\n",
    "            res = 0\n",
    "            i = 1\n",
    "            fives = []\n",
    "            for s in range(1, n+1):\n",
    "                if s == 5**i:\n",
    "                    res += i\n",
    "                    i += 1\n",
    "                    fives.append(s)\n",
    "                else:\n",
    "                    if str(s)[-1] in ['0', '5']:\n",
    "                        for j, x in enumerate(fives[::-1]):\n",
    "                            if s%x==0:\n",
    "                                res += len(fives)-j\n",
    "                                break\n",
    "            return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 1\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            count = count * i\n",
    "        \n",
    "        count = list(str(count))\n",
    "        for i in count[::-1]:\n",
    "            if i =='0':\n",
    "                res = res + 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        amount = 0\n",
    "        for i in range(1, n+1):\n",
    "            while i % 5 == 0:\n",
    "                amount += 1\n",
    "                i /= 5\n",
    "        return amount "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        o = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            c = i\n",
    "            while c % 5 == 0:\n",
    "                c /= 5\n",
    "                o += 1 \n",
    "\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res=0\n",
    "        num=1\n",
    "        for i in range(1,n+1):\n",
    "            num*=i\n",
    "        num=list(map(int,str(num)))\n",
    "        for i in num[::-1]:\n",
    "            if i==0:\n",
    "                res+=1\n",
    "            if i!=0:\n",
    "                break\n",
    "        return res\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5,n+1,5):\n",
    "            while i%5==0:\n",
    "                i//=5\n",
    "                ans+=1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        import math\n",
    "        result=0\n",
    "        for i in range(1,n+1):\n",
    "            if i%5 == 0:\n",
    "                while i>=5 and i%5==0:\n",
    "                    result=result+1\n",
    "                    i = i/5\n",
    "            else:\n",
    "                continue        \n",
    "        return int(result)            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "\n",
    "        while n:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        two_count = 0\n",
    "        five_count = 0\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(1, n + 1):\n",
    "            while i and i % 2 == 0:\n",
    "                # print('2:' + str(i))\n",
    "                two_count += 1\n",
    "                i //= 2\n",
    "            while i and i % 5 == 0:\n",
    "                # print('5:' + str(i))\n",
    "                five_count += 1\n",
    "                i //= 5\n",
    "        return min(two_count, five_count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        x = 0\n",
    "        for i in range(1,n+1):\n",
    "            a = i\n",
    "            while a % 5 == 0:\n",
    "                a = a / 5\n",
    "                x += 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n<5:\n",
    "            return 0\n",
    "        \n",
    "        result=0\n",
    "        while n>=5:\n",
    "            result+=n//5\n",
    "            n=n//5\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        #  find 5 的个数:\n",
    "        rt = 0\n",
    "        for i in range(1,n+1):\n",
    "            while (i%5==0):\n",
    "                i = i/5\n",
    "                rt+=1\n",
    "        return rt \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        zerocnt = 0\n",
    "        for i in range(5,n+1,5):\n",
    "            temp = i\n",
    "            while temp % 5 ==0:\n",
    "                zerocnt+=1\n",
    "                temp = temp // 5\n",
    "        return zerocnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        carry = 1\n",
    "        max_length = len(str(n)) + 1\n",
    "        for i in range(1, n + 1):\n",
    "            carry *= i\n",
    "            while carry % 10 == 0:\n",
    "                res += 1\n",
    "                carry //= 10\n",
    "            carry = int(str(carry)[-max_length:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # count = len(list(filter(lambda x: x % 5 == 0, range(1, n+1))))\n",
    "        count = 0\n",
    "        while(n>=5):\n",
    "            count += n //5\n",
    "            n = n // 5\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        while n >= 5:\n",
    "            res += n // 5\n",
    "            n //= 5\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n // 5 > 0:\n",
    "            res = res + n // 5\n",
    "            n //= 5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        sum0=0\n",
    "        while n>=5:\n",
    "            n=n//5\n",
    "            sum0+=n\n",
    "        return sum0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return int(n/5)+int(n/25)+int(n/125)+int(n/625)+int(n/3125)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n < 5:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            ans += n\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trailingZeroes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 0 来源于10的个数，10=2*5，2的个数远大于5，所以只需要计算5、5的n次方的个数\n",
    "        # n/5 + n/25 + n/125 + ...\n",
    "\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            res += n\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n = int(n/5)\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return sum(n // 5 ** i for i in range(1, 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trailingZeroes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n >= i:\n",
    "            count += n // i\n",
    "            i *= 5\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "\n",
    "        r = 0\n",
    "        while n>=5:\n",
    "            r+=n//5\n",
    "            n=n//5\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n // i > 0:\n",
    "            count += n // i\n",
    "            i *= 5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans =0\n",
    "        while n>=5:\n",
    "            ans += n//5\n",
    "            n = n//5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(0,n+1,5):\n",
    "            t = i\n",
    "            while t%5==0 and t>0:\n",
    "                t/=5\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            ret += n\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n//5>0:\n",
    "            res+=n//5\n",
    "            n=n//5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x):\n",
    "            c = 0\n",
    "            while x > 0 and x % 5 == 0:\n",
    "                c += 1\n",
    "                x = x // 5\n",
    "            return c\n",
    "        f5 = 0\n",
    "        for z in range(1, n + 1):\n",
    "            f5 += fac(z)\n",
    "        return f5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n+1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i = i // 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        i=5\n",
    "        count=0\n",
    "        while n//i: \n",
    "            count+=n//i\n",
    "            i*=5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans += n//5\n",
    "            n //= 5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count=0\n",
    "\n",
    "        while n>=5:\n",
    "            count+=n//5\n",
    "            n//=5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n // 5 + n // 25 + n // 125 + n // 625 + n // 3125"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def trailingZeroes(self, n: int) -> int:\n",
    "    ans = 0\n",
    "    while n:\n",
    "      n //= 5\n",
    "      ans += n\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp = i\n",
    "            while tmp % 5 == 0:\n",
    "                tmp /= 5\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n//5+n//25+n//125+n//625+n//3125"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        while n >=5:\n",
    "            n = n // 5\n",
    "            res += n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n // 5 + self.trailingZeroes(n // 5) if n // 5 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return n // 5 + self.trailingZeroes(n // 5) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        while n>0:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        t=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            t+=n\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "\n",
    "        count = 0 \n",
    "        \n",
    "        for i in range(5, n+1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5  # replace i with i // 5\n",
    "                count += 1\n",
    "\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n>=5:\n",
    "            count += int(n / 5);\n",
    "            n = n / 5;\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        p = 0\n",
    "        while n >= 5:\n",
    "            n = n // 5\n",
    "            p += n\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        fac = math.factorial(n)\n",
    "        res = 0\n",
    "        while fac % 10 == 0:\n",
    "            res += 1\n",
    "            fac //= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            res += n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,6):\n",
    "            if n // (5**i) == 0:\n",
    "                break\n",
    "            res += n // (5**i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 5! = 120, 有 1 个 0\n",
    "        # 不能直接阶乘是因为有溢出的可能性\n",
    "        # 所以就要找到什么情况才会产生 0\n",
    "        # 解题：对于阶乘过程的每个数，[1, n]，寻找质因数对 {2, 5} 的个数\n",
    "\n",
    "        def fac(x, y):\n",
    "            cnt = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                cnt += 1\n",
    "                x /= y\n",
    "            return cnt\n",
    "\n",
    "        cnt_2 = 0\n",
    "        cnt_5 = 0\n",
    "        for k in range(1, n+1):\n",
    "            cnt_2 += fac(k, 2)\n",
    "            cnt_5 += fac(k, 5)\n",
    "\n",
    "        return min(cnt_2, cnt_5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        divisor = 5\n",
    "\n",
    "        while n >= divisor:\n",
    "            res += n // divisor\n",
    "            divisor *= 5\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x, y):\n",
    "            c = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                c += 1\n",
    "                x /= y\n",
    "            return c\n",
    "        f2, f5 = 0, 0\n",
    "        for z in range(1, n + 1):\n",
    "            f2 += fac(z, 2)\n",
    "            f5 += fac(z, 5)\n",
    "        return f5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n//5:\n",
    "            res += n//5\n",
    "            n = n//5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        r = 0\n",
    "        for i in range(5, n+1, 5):\n",
    "            while i%5 ==0:\n",
    "                i //= 5\n",
    "                r += 1\n",
    "        return r \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n // i >= 1:\n",
    "            count += n//i\n",
    "            i = i * 5\n",
    "        return count \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x, y):\n",
    "            c = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                c += 1\n",
    "                x /= y\n",
    "            return c\n",
    "        f5 = 0\n",
    "        for z in range(1, n + 1):\n",
    "\n",
    "            f5 += fac(z, 5)\n",
    "        return f5\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
